class Node{
    constructor(element){
        this.element = element;
        this.left = null;
        this.right = null;
    }
}

class Tree{
    constructor(){
        this.root = null;
    }

    //insert 插入

    insert(element){
        //1.创建节点
        let node = new Node(element);

        if(this.root === null){
            this.root = node;
        }else{
            //
            this.insertNode(this.root,node);
        }
    }
    
    insertNode(rootNode,newNode){
        //1.判断当前节点和父节点进行比较 比父节点大，放在父节点的右侧，否则，放在父节点的左侧
        if(rootNode.element > newNode.element){
            //左侧
            if(rootNode.left === null){
                rootNode.left = newNode;
            }else{
                this.insertNode(rootNode.left,newNode);
            }
        }else{
            //右侧
            if(rootNode.right === null){
                rootNode.right = newNode;
            }else{
                this.insertNode(rootNode.right,newNode);
            }
        }
    }

    //最小值
    min(){
        return this.minNode(this.root);
    }

    minNode(node){
        while(node.left != null){
            node = node.left;
        }
        return node
    }

    max(){
        return this.maxNode(this.root);
    }

    maxNode(node){
        while(node.right != null){
            node = node.right;
        }
        return node
    }

    search(element){  //找到true，找不到返回false
        return this.searchNode(element,this.root);
    }

    //递归：终止条件  
    searchNode(element,rootNode){
        //终止条件
        if(rootNode === null){
            return false
        }

        if(element < rootNode.element){  //11
            //左侧
            return this.searchNode(element,rootNode.left); //true  false   7
        }else if(element > rootNode.element){
            //右侧
            return this.searchNode(element,rootNode.right);
        }else{
            //相等
            return true
        }
    }

    inOrderTraverse(callback){
        this.inOrderTraverseNode(this.root,callback);
    }

    inOrderTraverseNode(node,callback){
        if(node != null){
            this.inOrderTraverseNode(node.left,callback);
            callback(node.element);
            this.inOrderTraverseNode(node.right,callback);
        }
    }


    //前序遍历
    preOrderTraverse(callback){
        this.inOrderTraverseNode(this.root,callback);
    }

    preOrderTraverseNode(node,callback){
        if(node != null){
            callback(node.element);
            this.preOrderTraverseNode(node.left,callback);
            this.preOrderTraverseNode(node.right,callback);
        }
    }

    //后序遍历

    postOrderTraverse(callback){
        this.postOrderTraverseNode(this.root,callback);
    }

    postOrderTraverseNode(node,callback){
        if(node != null){
            this.postOrderTraverseNode(node.left,callback);
            this.postOrderTraverseNode(node.right,callback);
            callback(node.element);
        }
    }


    //删除
    remove(element){
        this.root = this.removeNode(element,this.root);
    }

    removeNode(element,node){
        if(node === null){
            return null
        }

        if(element < node.element){
            //左侧
            node.left = this.removeNode(element,node.left);
            return node;
        }else if(element > node.element){
            //右侧
            node.right = this.removeNode(element,node.right);
            return node;
        }else{
            //相等
            //1.叶子
            if(node.left === null && node.right === null){
                node = null;
                return node;
            }
            //2.只有一个子节点
            if(node.left === null){
                //有右侧子节点
                return node.right
            }else  if(node.right === null){
                //有左侧子节点
                return node.left;
            }

            //3.两个子节点
            let minNode = this.minNode(node.right);// 15
            console.log("======",minNode);
            node.element = minNode.element; //18 放在了15的位置
            node.right = this.removeNode(node.element,node.right);
            return node
        }
    }

    maxDepth(){
        return this.depth(this.root)  //最大深度
    }

    depth(node){
        if(node === null){
            return 0
        }

        let leftDepth = this.depth(node.left);
        let rightDepth = this.depth(node.right);

        let num = leftDepth > rightDepth ? leftDepth : rightDepth;

        return num+1
    }
}

let tree  = new Tree();

tree.insert(11);

tree.insert(7);

tree.insert(5);

tree.insert(6);

tree.insert(3);

tree.insert(15);

tree.insert(13);

tree.insert(20);

tree.insert(18);

tree.insert(25);

console.log(tree.maxDepth());

// console.log(tree.min())

// console.log(tree.search(7))



//1. 把快速排序  2.队列和栈   3.树  

// let callback = (element) => {
//     console.log(element)
// }

// tree.preOrderTraverse(callback);

tree.remove(6)
tree.remove(5);

tree.remove(15)
console.log(tree);

